package com.example.interview;

import java.util.Arrays;

public class Client {

    public static void main(String[] args) {
        int n;
        // 当数据量稍微比较大时，递归由于重复计算子问题且子问题数量快速增多导致耗时指数级增长
        for (int i = 1; i < 30; i++) {
            n = i;
            System.out.println("计算" + n);
            long start = System.nanoTime();
            int res = dp(n);
            System.out.println(res);
            long end = System.nanoTime();
            System.out.println("dp耗时" + (end - start) * 1.0 / Math.pow(10, 6) + "ms");

            start = System.nanoTime();
            int res1 = resolve(n);
            System.out.println(res1 == res);
            end = System.nanoTime();
            System.out.println("递归耗时" + (end - start) * 1.0 / Math.pow(10, 6) + "ms");
            System.out.println(" ");
        }
    }

    /**
     * 简单递归会超时，对于重叠子问题进行了重复计算，应该使用记忆化递归计算中间递归结果
     *
     * @param n
     * @return
     */
    private static int resolve(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return -1;
        }
        if (n == 2 || n == 3 || n == 7 || n == 11 || n == 17) {
            return 1;
        }
        int lastMin = Integer.MAX_VALUE;
        lastMin = updateLastMin(lastMin, n - 2);
        lastMin = updateLastMin(lastMin, n - 3);
        lastMin = updateLastMin(lastMin, n - 7);
        lastMin = updateLastMin(lastMin, n - 11);
        lastMin = updateLastMin(lastMin, n - 17);
        if (lastMin == Integer.MAX_VALUE) {
            return -1;
        }
        return lastMin + 1;
    }

    private static int updateLastMin(int lastMin, int index) {
        if (index >= 0) {
            int last = resolve(index);
            if (last > 0) {
                lastMin = Math.min(lastMin, last);
            }
        }
        return lastMin;
    }

    private static int dp(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return -1;
        }
        if (n == 2 || n == 3 || n == 7 || n == 11 || n == 17) {
            return 1;
        }
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        // 地面，不用下
        dp[0] = 0;
        // 第一阶，下不来
        if (n >= 1) {
            dp[1] = -1;
        }
        // 以下只需一步
        if (n >= 2) {
            dp[2] = 1;
        }
        if (n >= 3) {
            dp[3] = 1;
        }
        if (n >= 7) {
            dp[7] = 1;
        }
        if (n >= 11) {
            dp[11] = 1;
        }
        if (n >= 17) {
            dp[17] = 1;
        }
        for (int i = 1; i <= n; i++) {
            if (dp[i] != Integer.MAX_VALUE) {
                continue;
            }
            if (checkPrev(dp, i - 2)) {
                dp[i] = Math.min(dp[i], dp[i - 2] + 1);
            }
            if (checkPrev(dp, i - 3)) {
                dp[i] = Math.min(dp[i], dp[i - 3] + 1);
            }
            if (checkPrev(dp, i - 7)) {
                dp[i] = Math.min(dp[i], dp[i - 7] + 1);
            }
            if (checkPrev(dp, i - 11)) {
                dp[i] = Math.min(dp[i], dp[i - 11] + 1);
            }
            if (checkPrev(dp, i - 17)) {
                dp[i] = Math.min(dp[i], dp[i - 17] + 1);
            }
            if (dp[i] == Integer.MAX_VALUE) {
                dp[i] = -1;
            }
        }
        return dp[n];
    }

    private static boolean checkPrev(int[] dp, int index) {
        return index >= 0 && dp[index] > 0;
    }
}
